This invention is related to the construction of efficient homomorphic encryption systems, in particular, fully homomorphic encryption, where any computation can be performed on encrypted data to protect the secrecy and the privacy of the data.
In our modern information systems, users often have their data stored and managed on large servers or clouds, which they do not have real control, for example, users may store their data in an Amazon cloud. However from the perspective of the users, the secrecy and the privacy of the data becomes a serious concern, since the server has the full control of the data.
One solution to this problem is that the users instead encrypt their data using a symmetric cryptosystem like AES with their own keys and store it in a cloud such that only each user can decrypt the data with their own keys. However this present another problem in the sense that the users can not make full use of the advantage of the powerful computing power to process the data since for a usual encryption like AES we can not perform meaningful operation on encrypted data. This diminishes tremendously the advantage of using the clouds.
Homomorphic encryption is a type of encryption scheme which allows computations over the encrypted data, namely the ciphertext, and derive an encrypted result when decrypted, gives result of computations performed over the plaintext. The feature is very suitable for privacy protection and for cloud computing.
The power of fully homomorphic encryption was recognized within a year of the development of RSA and there are efficient (partially) homomorphic systems, where only certain type of computations on the encrypted data like addition (only) can be performed on the encrypted data.
An idea solution to the problem is to use what is called fully homomorphic encryption (FHE) systems, where any computation can be performed on the encrypted data. Theoretically speaking, a cryptosystem which supports both addition and multiplication on encrypted data is a fully homomorphic encryption (FHE). FHE allows programs to run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, therefore it can be run by an untrusted third party without revealing any information on the processed information.
But only after 30 years of the initial suggestion of the idea of homomorphic encryption, recently a number of FHE systems are proposed. The first one was proposed by Craig Gentry in 2009. Craig Gentry used lattice cryptography to build the first FHE system.
Theoretically Gentry's system can provide evaluations of arbitrary depth circuits (any algebraic computations), but his construction starts from a somewhat homomorphic encryption scheme with a limit on essentially the degree of polynomials that can be computed over encrypted data. Then he built a technique called bootstrap, which is essentially to actually evaluate its own decryption circuit, to build a fully homomorphic encryption. But this step is very costly practically and therefore the systems is not efficient.
There are different variants of Gentry's scheme with smaller key and ciphertext sizes, but still not practical.
There are constructions based on Integers, Learning With Errors problems (LWE) and Ring Learning with Errors problems (RLWE), which are more efficient but again they require bootstrap and the systems are not efficient and not practical.